package com.shuang.dp7;

class Solution {
    public int numTrees(int n) {
        //dp数组 dp[i]表示从1到i一共有不同的d[i]个二叉搜索树 也就是i个不同元素组成的不同二叉搜索树d[i]个
        int[] dp = new int[n + 1];

        //递归公式
        //从1作为头节点时 左子树不同元素组成的数量*右子树不同元素组成的数量 加上 2作为头节点 一直到n作为头节点时
        //用j从1开始遍历作为各个头节点

        //初始化数组 没有元素时 空节点的树也是一个二叉搜索树合理 并且dp[0]=1符合程序运行 
        dp[0] = 1;
        dp[1] = 1;//不初始化这个也可以在下面求出来 初始化下面从2开始

        //遍历顺序 从前到后
        for (int i = 2; i <= n; i++){
            for (int j = 1; j <= i; j++){
                //二叉搜索树特性 左子树一定小于头节点所以j为头节点 从1到i个数中 小于j的一共 j-1个数 一定都在左子树
                //右子树都大于头节点 一共从1到i个元素 i-j个元素在右子树
                //所以递归如下
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }
}